(define EX1-14-TEST-NUM 100000)

; Basic a^n mod n
; (define (asn a n)
;     (cond   ((= n 0) 1)
;             ((even? n)
;                 (* (square (asn a (/ n 2)))))
;             (else
;                 (* a (asn a (- n 1))))))

; (define (expmod base exp m)
;     (remainder (asn base exp) m))

; Fast a^n mod n
(define (expmod base exp m)
    (cond   ((= exp 0) 1)
            ((even? exp)
                (remainder (square (expmod base (/ exp 2) m))
                    m))
            (else
                (remainder (* base (expmod base (- exp 1) m))
                    m))))

(define (fermat-test n)
    (define (try-it a)
        (= (expmod a n n) a))
    (try-it (+ 1 (random (- n 1)))))

(define (fast-primes? n times)
    (cond ((= times 0) true)
          ((fermat-test n) (fast-primes? n (- times 1)))
          (else false)))

(define (next-odd n)
    (if (odd? n)
        (+ n 2)
        (+ n 1)))

(define (continue-primes n count)
    (cond   ((= count 0)
                (display "are primes."))
            ((fast-primes? n 3)
                (display n)
                (newline)
                (continue-primes (next-odd n) (- count 1)))
            (else
                (continue-primes (next-odd n) count))))

(define (search-for-primes n)
    (let ((start-time (real-time-clock)))
        (continue-primes n 10)
        (display "\nconsumed time: ")
        (display (- (real-time-clock) start-time))
        (display " ms")))

(display "\n========================================\n")
(search-for-primes EX1-14-TEST-NUM)
; (display (fast-primes? 100 10))
; (display (continue-primes 10 2))
; (display (expmod 5 11 11))
(display "\n========================================\n")
